1. Technical Field
The present invention relates to an adaptable motion estimator architecture for low bit rate image communication. Particularly, the present invention relates to a technique to implement a motion estimator which has a reduced size of hardware and is compatible with characteristics and a bit rate of an applied image.
2. Description of the Prior Art
Generally, an image data compression/decompression technique is an essential one used in various fields such as multimedia communication, broadcast, storing media, etc. There are several standards for the image data compression/decompression such as JPEG (Joint Photographic Experts Group), MPEG (Moving Picture Experts Group), H.261/H.263, etc. Among them, H.261/H.263 is broadly used for low bit rate image communication.
Particularly, there are two methods of compressing the moving pictures: spatial compression and time compression. The spatial compression mainly employs DCT (Discrete Cosine Transform), Huffman Coding, DPCM (Differential Pulse Code Modulation), RLC (Run Length Coding), and so on. The time compression mainly uses Motion Estimation.
The motion estimation enhances the bit rate by obtaining a moving vector corresponding to a position with the least difference in a given search area of a previous frame to send a 16×16 macro block of a current frame by using a time relation between the previous frame and the current frame. The motion estimation is used in all encoders to which MPEG and H.261/H.263 standards are applied.
FIG. 1 is a schematic view for illustrating concept of a macro block in the current frame.
As shown in FIG. 1, a size of the macro block in the current frame is indicated in 16 pixels×16 pixels by the MPEG and H.261/H.263 standards and defined as a macro block 10.
In case of a CIF (Common Interchange Format) having a current frame size of 352 pixels×288 pixels, 396 macro blocks 10 exists in each frame and 396 times of motion estimations are needed.
In case of ¼ CIF (Quarter CIF; hereinafter referred as QCIF) having a current frame size of 176 pixels×144 pixels, it can be understood that 99 times of motion estimations are needed in one frame.
FIG. 2 is a schematic view for illustrating concept of a search window and a motion vector.
As shown in FIG. 2, the current macro block 10 in a current frame moves in a pixel unit on a search area of a previous frame and finds a macro block having a least difference.
At this time, a position of the current macro block 10 and a position of a best match block 20 are indicated as a motion vector 30 on the previous frame.
Computational complexity and memory bandwidth of the motion estimator may estimate motion as shown in FIG. 2 when using a full search method, which is a representative motion estimating method.
Of course, provided that a size of the macro block is 16 pixels×16 pixels and a distance of the search window is 8, the numbers of available vectors are −8˜+8 at X-axis and −8˜+8 at Y-axis. Also, 289 times of comparisons are required for 17 pixel×17 pixel macro blocks.
In order to find out the most similar macro block 10 among the 289 motion vectors, MAE (Mean Absolute Error) is mainly used and a value corresponding to a least MAE is determined as the motion vector 30.
MAE is obtained by adding an absolute value of a difference between a current pixel and a previous pixel, which is identical to a value adding an absolute value of a 16 pixel×16 pixel difference.
In other word, because there are all 99 macro blocks in QCIF and MAE requires 289 calculations for each block, about 99×289 (28,611) times of MAE calculations are needed in one frame.
In fact, MAE calculations are performed less than 28,611 times. Because the search area is limited for macro blocks in a frame boundary, 23,427 times of macro block comparisons are needed in consideration of the boundary.
Such motion estimation requires much computational complexity and very large memory bandwidth, which make it difficult to implement such technique into hardware.
The previous frame data and the current frame data are generally stored in DRAM (Dynamic Random Access Memory). The reason is that there is quite a large amount of the frame data. For example, about one MEGA bit memory is required to store one frame of CIF.
In addition, in order to access a comparison macro block data of the previous frame from DRAM whenever comparing the macro blocks, a very large memory bandwidth is needed.
As shown in FIG. 2, in case of QCIF, an image format and a moving picture of 15 frames per second, 23,427×16×16×15 bytes/second (about 90 Mbytes/second) of memory bandwidth is required. Due to such big memory access, a high speed SRAM (Static RAM) is usually used as a cache memory.
FIG. 3 shows a half-pixel position and its formula among the moving vectors of FIG. 2.
As shown in FIG. 3, capital letter A, B, C and D points indicate integer-pixel positions, while small letter a, b, c and d points indicate half-pixel positions. In the figure, it can be seen that there exist integer-pixel vectors and half-pixel vectors in the motion vector.a=Ab=(A+B+1)/2c=(A+C+1)/2d=(A+B+C+D+2)/2  Formula 1
Therefore, motion of the half-pixel position can be estimated by the above Formula 1 using each of the integer-pixels and the half-pixels.
However, such conventional motion estimation has some problems described below.
First, the conventional motion estimation requires a large amount of computational complexity. Though a faster search algorithm such as a hierarchy search, a three step search, a sub-sampling search, etc. is announced to reduce the computational complexity, such search methods have difficulties in hardware applications. Therefore, the full search algorithm is mainly used.
Second, as a hardware structure for the full search, a systolic array is usually used. However, the systolic array has a drawback that it may increase a size of hardware and a load of synchronous clocks due to abundant registers for pipelines.
Third, in case of using the systolic array, a half-pixel function can be hardly included in an integer-pixel function. So, a separate hardware for the half-pixel function is needed.